package offer.offer02;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 *
 */
public class S32II从上到下打印二叉树 {
    /**
     * 94
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) return new LinkedList<>();
        List<List<Integer>> res = new LinkedList<>();
        List<TreeNode> nodeList1 = new ArrayList<>();
        List<TreeNode> nodeList2 = new ArrayList<>();
        nodeList1.add(root);
        while(nodeList1.size() != 0){
            List<Integer> resEle = new ArrayList<>();
            for(TreeNode tempNode: nodeList1){
                resEle.add(tempNode.val);
                if(tempNode.left != null) nodeList2.add(tempNode.left);
                if(tempNode.right != null) nodeList2.add(tempNode.right);
            }
            res.add(resEle);
            nodeList1 = nodeList2;
            nodeList2 = new ArrayList<>();
        }
        return res;
    }

    /**
     * 别人的层序遍历。用queue比较好, 就栈。
     */
    public List<List<Integer>> levelOrder2(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--) {
                // 这里实际上没有切换栈, 用size做限制, 就是queue不太熟。
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }

}
